package DP1;

/**
 * 152. 乘积最大子数组
 * 输入: [2,3,-2,4]
 * 输出: 6
 * 解释: 子数组 [2,3] 有最大乘积 6。
 */
public class Main8 {
    public static void main(String[] args) {

    }

    public static int maxProduct(int[] nums) {
        int n = nums.length;
        int[] maxDP = new int[n];
        int[] minDP = new int[n];
        maxDP[0] = nums[0];
        minDP[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            maxDP[i] = Math.max(nums[i],Math.max(maxDP[i-1]*nums[i],minDP[i-1]*nums[i]));
            minDP[i] = Math.min(nums[i],Math.min(maxDP[i-1]*nums[i],minDP[i-1]*nums[i]));
        }

        int max = Integer.MIN_VALUE;
        for (int e : maxDP){
            max = Math.max(max,e);
        }
        return max;
    }
}
